﻿namespace FiniteAutomaton
{
    using System.Collections.Generic;
    using System.Linq;

    public class Converter
    {
        public static NondeterministicFiniteAutomaton ConvertNFAToDFA(NondeterministicFiniteAutomaton nfa)
        {
            // Reference: Fig 3.25, Aho, Sethi, and Ullman
            NondeterministicFiniteAutomaton result = new NondeterministicFiniteAutomaton();

            // Mapping from a DFA state to corresponding NFA states (the subset).
            Dictionary<State, HashSet<State>> stateToSubsetMapping = new Dictionary<State, HashSet<State>>();
            List<State> unmarkedStates = new List<State>();

            // Initially, e-closure(s0) is the only state in Dstates and it is unmarked.
            HashSet<State> nfaStartStateSet = new HashSet<State>();
            nfaStartStateSet.Add(nfa.States.PeekFront());

            State sp = new State();
            stateToSubsetMapping[sp] = EpsilonClosure(nfa, nfaStartStateSet);
            result.States.AddBack(sp);
            unmarkedStates.Add(sp);

            // while there is an unmarked state T in Dstates do
            while (unmarkedStates.Count() > 0)
            {
                // mark T
                State unmarked = unmarkedStates[0];
                unmarkedStates.RemoveAt(0);

                // Collect the set of inputs of T;
                IEnumerable<char> inputSet = nfa.Transitions.Where(t => t.Label != (char)0 && stateToSubsetMapping[unmarked].Contains(t.Source)).Select(t => t.Label);

                foreach (char ch in inputSet)
                {
                    // Get a subset of states reachable from current subset via a ch transition
                    HashSet<State> subset = EpsilonClosure(nfa, Move(nfa, ch, stateToSubsetMapping[unmarked]));

                    // Check if the subset is already a state in the DFA
                    State u = result.States.Where(s => stateToSubsetMapping[s].SetEquals(subset)).FirstOrDefault();

                    // If not, create a new state and add it to the DFA
                    if (u == default(State))
                    {
                        u = new State();
                        stateToSubsetMapping[u] = subset;
                        unmarkedStates.Add(u);
                        result.States.AddBack(u);
                    }

                    // Add a transition in the DFA
                    result.Transitions.Add(new LabeledEdge<State, char>(unmarked, u, ch));
                }
            }

            return result;
        }

        public static HashSet<State> EpsilonClosure(NondeterministicFiniteAutomaton nfa, IEnumerable<State> states)
        {
            // Reference: Fig 3.26, Aho, Sethi, and Ullman
            HashSet<State> result = new HashSet<State>(states);
            Stack<State> unprocessedStates = new Stack<State>(states);

            while (unprocessedStates.Count() > 0)
            {
                // Remove the first state from the unprocessed states
                State state = unprocessedStates.Pop();

                // Get all epsilon transitions for this state
                IEnumerable<State> epsilonStates = nfa.Transitions.Where(t => t.Source == state && t.Label == (char)0).Select(t => t.Target);

                // For each state u reachable via an e-transition, add it to the result
                // as well as the set of unprocessed states
                foreach (State u in epsilonStates)
                {
                    if (!result.Contains(u))
                    {
                        result.Add(u);
                        unprocessedStates.Push(u);
                    }
                }
            }

            return result;
        }

        public static HashSet<State> Move(NondeterministicFiniteAutomaton nfa, char ch, HashSet<State> states)
        {
            HashSet<State> result = new HashSet<State>();
            foreach (LabeledEdge<State, char> t in nfa.Transitions.Where(t => states.Contains(t.Source) && t.Label == ch))
            {
                result.Add(t.Target);
            }

            return result;
        }
    }
}